package leetcode.editor.cn.q1_300.q50;

class UniquePathsIi {
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int uniquePathsWithObstacles(int[][] obstacleGrid) {
            int m = obstacleGrid.length;
            int n = obstacleGrid[0].length;
            if (obstacleGrid[m - 1][n - 1] == 1) return 0;

            int[][] arr = new int[m][n];

            int step = 1;
            for (int i = 0; i < m; i++) {
                if (obstacleGrid[i][0] == 1) step = 0;
                arr[i][0] = step;
            }

            step = 1;
            for (int i = 0; i < n; i++) {
                if (obstacleGrid[0][i] == 1) step = 0;
                arr[0][i] = step;
            }

            for (int i = 1; i < m; i++) {
                for (int j = 1; j < n; j++) {
                    if (obstacleGrid[i - 1][j] == 1 && obstacleGrid[i][j - 1] == 1) {
                        arr[i][j] = 0;
                        continue;
                    }
                    if (obstacleGrid[i - 1][j] == 1) {
                        arr[i][j] = arr[i][j - 1];
                    } else if (obstacleGrid[i][j - 1] == 1) {
                        arr[i][j] = arr[i - 1][j];
                    } else {
                        arr[i][j] = arr[i - 1][j] + arr[i][j - 1];
                    }
                }
            }

            return arr[m - 1][n - 1];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new UniquePathsIi().new Solution();
        System.out.println(solution.uniquePathsWithObstacles(new int[][]{
                {0, 0, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 1, 0, 0}
        }));
    }
}